package algorithm_demo.demo05;

/**
 * @author Api
 * @date 2023/3/17 0:19
 */
public class Code10_RobotWalk1 {
    /*暴力递归方式*/

    /**
     * @param N N个位置
     * @param M M初始位置
     * @param K 走K步
     * @param P 目标P
     * @return
     */
    public static int way1(int N, int M, int K, int P) {
        if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
            return 0;
        }
        return process1(N, M, K, P);
    }

    public static int process1(int N, int cur, int rest, int P) {
        if (rest == 0) {//base case
            return cur == P ? 1 : 0;
        }
        //在1位置时，只能向右走
        if (cur == 1) {
            return process1(N, 2, rest - 1, P);
        }
        //在最后一个位置时，只能往左走
        if (cur == N) {
            return process1(N, N - 1, rest - 1, P);
        }
        //中间位置
        return process1(N, cur + 1, rest - 1, P) + process1(N, cur - 1, rest - 1, P);
    }

    /*动态规划*/
    public static int way2(int N, int M, int K, int P) {
        if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
            return 0;
        }
        int[][] dp = new int[N + 1][K + 1];
        //初始化dp
        for (int row = 0; row <= N; row++) {
            for (int col = 0; col <= K; col++) {
                dp[row][col] = -1;
            }
        }
        return process1(N, M, K, P, dp);
    }

    /*记忆性搜索-动态规划，从重复性入手，并且根据可变参数，设置dp数组*/
    /*还可以使用缓存的方式来进行HashMap<String, Integer> map key: 10_100, 10*/
    public static int process1(int N, int cur, int rest, int P, int[][] dp) {
        if (dp[cur][rest] != -1) {
            return dp[cur][rest];
        }
        if (rest == 0) {
            dp[cur][rest] = cur == P ? 1 : 0;
            return dp[cur][rest];
        }
        if (cur == 1) {
            dp[cur][rest] = process1(N, 2, rest - 1, P, dp);
            return dp[cur][rest];
        }
        if (cur == N) {
            dp[cur][rest] = process1(N, N - 1, rest - 1, P, dp);
            return dp[cur][rest];
        }
        dp[cur][rest] = process1(N, cur + 1, rest - 1, P, dp) + process1(N, cur - 1, rest - 1, P, dp);
        return dp[cur][rest];
    }

    /*不是所有的暴力递归都可以搞成动态规划，是所有的动态规划，都来自于一个递归*/
    public static void main(String[] args) {
        System.out.println(way1(7, 2, 5, 3));
        System.out.println(way2(6, 3, 3, 2));

        System.out.println(way3(7, 2, 5, 3));
        System.out.println(way3(6, 3, 3, 2));
    }

    /*经典动态规划*/
    public static int way3(int N, int M, int K, int P) {
        if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
            return 0;
        }
        int[][] dp = new int[N + 1][K + 1];
        return process2(N, M, K, P, dp);
    }

    /**
     * 首先理解dp创建后默认值均为0,
     *
     * @param N  长度1-N
     * @param M  当前位置
     * @param K  剩余步数
     * @param P  目标位置
     * @param dp dp数组
     * @return 返回方法数
     */
    public static int process2(int N, int M, int K, int P, int[][] dp) {
        //有效范围为rest=0;cur=P;
        dp[P][0] = 1; //当前dp[目标位置][rest=0] = 1
        //有效范围为rest=1,cur=2
        for (int rest = 1; rest <= K; rest++) {
            //dp[i][j] i表示为当前位置， j表示剩余的步数
            //有效范围：cur=1时
            dp[1][rest] = dp[2][rest - 1];
            for (int cur = 2; cur < N; cur++) {
                //中间位置
                dp[cur][rest] = dp[cur + 1][rest - 1] + dp[cur - 1][rest - 1];
            }
            //有效范围：cur=N时
            dp[N][rest] = dp[N - 1][rest - 1];
        }
        return dp[M][K];
    }
}
